#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define str string
#define all(x) (x).begin(),(x).end()
#define ms(a,t) memset(a,t,sizeof(a))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define db double
#define lowbit(x) ((x)&(-(x)))
const int maxn = 1e6+10;
const int mod = 998244353;
const ll INF = 0x3f3f3f3f;
const db eps = 1e-7;
int n,m,C;
vector<int> num;
struct KTT{
	pll t[maxn<<2]; ll k[maxn<<2]; ll tg[maxn<<2],tg2[maxn<<2],cov[maxn<<2]; // idx / const
	void work(int p,ll v) {
		t[p].fi += t[p].se * v; tg[p] += v; 
	}
	void work2(int p,ll v) {
		t[p].fi += v; tg2[p] += v; 
	}
	void work3(int p,ll v) {
		t[p].fi = v; tg2[p] = tg[p] = 0; cov[p] = v; t[p].se = k[p];
	}
	void push_up(int p) {
		t[p] = min(t[p<<1],t[p<<1|1]);
	}
	void push_down(int p) {
		if(cov[p] != -1) {
			work3(p<<1,cov[p]);
			work3(p<<1|1,cov[p]);
			cov[p] = -1;
		}
		if(tg2[p]) {
			work2(p<<1,tg2[p]);
			work2(p<<1|1,tg2[p]);
			tg2[p] = 0;
		}
		if(tg[p]) {
			work(p<<1,tg[p]);
			work(p<<1|1,tg[p]);
			tg[p] = 0;
		}
		push_up(p);
	}
	void modify(int p,int l,int r,ll v,int L = 1,int R = m) {
//		cerr<<p<<' '<<l<<' '<<r<<' '<<v<<' '<<L<<' '<<R<<'\n';
		int mid = (L + R) >> 1;
		if(l <= L && R <= r) {
			work(p,v);
			return;
		}
		push_down(p);
		if(l <= mid) modify(p<<1,l,r,v,L,mid);
		if(r > mid) modify(p<<1|1,l,r,v,mid+1,R);
		push_up(p);
	}
	void add(int p,int l,int r,ll v,int L = 1,int R = m) {
		if(l <= L && R <= r) {
			work2(p,v);
			return;
		}
		int mid = (L + R) >> 1;
		push_down(p);
		if(l <= mid) add(p<<1,l,r,v,L,mid);
		if(r > mid) add(p<<1|1,l,r,v,mid+1,R);
		push_up(p);
	}
	void update(int p,int l,int r,ll v,int L = 1,int R = m) {
		if(l <= L && R <= r) {
			work3(p,v);
			return;
		}
		int mid = (L + R) >> 1;
		push_down(p);
		if(l <= mid) update(p<<1,l,r,v,L,mid);
		if(r > mid) update(p<<1|1,l,r,v,mid+1,R);
		push_up(p);
	}
	ll query(int p,int l,int r,int L = 1,int R = m) {
		if(l <= L && R <= r) {
			return t[p].fi;
		}
		int mid = (L + R) >> 1;
		push_down(p);
		if(r <= mid) return query(p<<1,l,r,L,mid);
		if(l > mid) return query(p<<1|1,l,r,mid+1,R);
		return min(query(p<<1,l,r,L,mid),query(p<<1|1,l,r,mid+1,R));
	} 
	void build(int p,int L = 1,int R = m) {
		cov[p] = -1; k[p] = num[L-1];
		if(L == R) {
			t[p] = MP(0,num[L-1]);
			return;
		}
		int mid = (L + R) >> 1;
		build(p<<1,L,mid); build(p<<1|1,mid+1,R);
		push_up(p);
	}
	int lower_bound(int p,ll v,int L = 1,int R = m) {
		if(L == R) {
//			cerr<<L<<' '<<t[p].fi<<' '<<v<<' '<<t[p].se<<'\n';
			if(t[p].fi >= v) return L;
			return L+1;
		}
		push_down(p);
		int mid = (L + R) >> 1;
		if(t[p<<1|1].fi < v) return lower_bound(p<<1|1,v,mid+1,R);
		return lower_bound(p<<1,v,L,mid);
	}
}tr;
int a[maxn];
void Solve() {
	cin >> n;
	cin >> C;
	for(int i = 1; i <= n; i++) {
		cin >> a[i]; num.pb(a[i]);
	}
	sort(all(num)); num.erase(unique(all(num)),num.end()); m = num.size();
	tr.build(1);
	for(int i = 1; i <= n; i++) {
//		cerr<<i<<'\n';
		int p = lower_bound(all(num),a[i])-num.begin()+1;
		if(p > 1) {
			tr.add(1,1,p-1,C);
		}
		if(p < m) {
			tr.modify(1,p+1,m,1);
			tr.add(1,p+1,m,-a[i]);
		}
		ll val = tr.query(1,p,m);
		int l = tr.lower_bound(1,val);
//		if(l != p) cerr<<l<<' '<<p<<' '<<val<<' '<<tr.query(1,1,1)<<'\n';
//		assert(tr.query(1,l,p) >= val);
		tr.update(1,l,p,val);
//		for(int j = 1; j <= m; j++) cout<<tr.query(1,j,j)<<' '; cout<<'\n';
	}
	cout<<tr.query(1,1,m)<<'\n';
}
int main() {
	freopen("minimize.in","r",stdin);
	freopen("minimize.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	int TT; cin >> TT; while(TT--)
	Solve();
	return 0;
}
